"""
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n))
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
"""

#时间复杂度：O ((m+n) log (m+n))
def cul_mid_num(nums1, nums2):
    sum_num = nums1 + nums2
    sort_sum = sorted(sum_num)
    n = len(sum_nums)
    if n % 2 != 0:
        mid = sum_nums[n // 2]
    else:
        mid = (sum_nums[n // 2] + sum_nums[n // 2 - 1]) / 2.0
    return mid
    return mid_num

#使用二分查找的方式，不用合并排序
def median_finder(nums1, nums2):
    #1. 在最短的数组上做二分查找：避免分割点越界，减少二分查找的次数
    if len(nums2) < len(nums1):
        nums1, nums2 = nums2, nums1
    m = len(nums1)
    n = len(nums2)

    #2. 初始化二分边界和总左半长度
    left , right = 0, m
    total_left = (m + n + 1) // 2

    while left <= right:
        #3.1计算当前分割点i，j
        i = (left + right) // 2
        j = total_left - i

        #3.2处理边界情况：避免数组越界
        nums1_left_max = float('-inf') if i==0 else nums1[i-1]
        nums1_right_min = float('inf') if i==m else nums1[i]

        nums2_left_max = float('-inf') if j==0 else nums2[j-1]
        nums2_right_min = float('inf') if j==n else nums2[j]

        #3.3 检查大小平衡，找到正确的分割点
        if nums1_left_max <= nums2_right_min and nums1_right_min >= nums2_left_max:
            #4.根据奇数偶数计算中位数
            if (m + n) % 2 == 1:
                #奇数：左半边的最大值
                return max(nums2_left_max, nums1_left_max)
            else:
                #偶数：左半边的最大值和右半边的最小值的均值
                return (max(nums2_left_max, nums1_left_max) +
                        min(nums1_right_min, nums2_right_min)) / 2.0
        #3.4：调整二分范围
        elif nums1_left_max > nums2_right_min:
            #nums1左边太大，i左移
            right = i -1

        else:
            #nums2左边大于nums1的右边，i右移
            left = i + 1

    raise ValueError("输入的数组不是有序的")


if __name__ == '__main__':
    nums1 = [1, 3]
    nums2 = [2]
    # nums1 = [1, 2]
    # nums2 = [3, 4]
    # print(cul_mid_num(nums1, nums2))
    print(median_finder(nums1, nums2))